// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

//----------------------------------------------------------------------
// Lock::Lock
// 	Initialize a lock, so that it can be used for synchronization.
//----------------------------------------------------------------------
Lock::Lock(char* debugName)
{
	name = debugName;
	isFree = true; //True if the lock is not currently held by any thread
	lockOwner = NULL; //The thread that currently holds the lock
	waitingList = new List; //A list of threads waiting to acquire this lock
}
//----------------------------------------------------------------------
// Lock::~Lock
// 	De-allocate the lock. Assume no threads are waiting on the lock or currently holding it.
//----------------------------------------------------------------------
Lock::~Lock()
{
	delete waitingList;
}
//----------------------------------------------------------------------
// Lock::Acquire
// 	Allow a thread to take ownership of the lock or wait for it if another
//  thread already owns it
//----------------------------------------------------------------------
void Lock::Acquire()
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //Disable interrupts
	if(isFree) //If this lock is not currently held by any thread
	{
		lockOwner = currentThread; //The current thread now holds this lock
		isFree = false; //The lock is now held and no longer available for use by other threads
	}
	else if(isHeldByCurrentThread() == false) //If the thread is not the lock owner
	{
		waitingList->Append((void *)currentThread); //Add the thread onto a waiting list for the lock
		currentThread->Sleep(); //And put the thread to sleep
	}
	(void) interrupt->SetLevel(oldLevel); //Restore interrupts
}
//----------------------------------------------------------------------
// Lock::Release
// 	Makes the current thread release the lock and, if there are threads
//  in the waiting list for the lock, sets the next one in line as the new
//  owner of the lock
//----------------------------------------------------------------------
void Lock::Release()
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //Disable interrupts
	if(isHeldByCurrentThread() == false) //If the current thread is not the lock owner
	{
		printf("Error caught: %s is trying to release a lock it does not own!\n", currentThread->getName());
	}
	else if(waitingList->IsEmpty() == false) //If a thread is waiting for the lock
	{
		Thread* thread = (Thread *)waitingList->Remove(); //Remove the next thread from the lock's waiting list
	    scheduler->ReadyToRun(thread); //Put that thread in the ready state
	    lockOwner = thread; //Make that thread the lock owner
	}
	else
	{
	    lockOwner = NULL; //Clear lock ownership
		isFree = true; //Make the lock free
	}
	(void) interrupt->SetLevel(oldLevel); //Restore interrupts
}
//----------------------------------------------------------------------
// Lock::isHeldByCurrentThread
// 	Checks if the thread calling this function currently has ownership of this lock
//----------------------------------------------------------------------
bool Lock::isHeldByCurrentThread()
{
	if(currentThread == lockOwner)
		return true;
	else
		return false;
}

//----------------------------------------------------------------------
// Condition::Condition
// 	Initialize a condition, so that it can be used for synchronization.
//----------------------------------------------------------------------
Condition::Condition(char* debugName)
{
	name = debugName;
	waitingLock = NULL; //The lock waiting to acquire the condition
	waitingList = new List; //A list of threads waiting for the condition
}
//----------------------------------------------------------------------
// Condition::~Condition
// 	De-allocate the condition.
//----------------------------------------------------------------------
Condition::~Condition()
{
	waitingLock = NULL;
	delete waitingList;
}
//----------------------------------------------------------------------
// Condition::Wait
// 	Add the thread to the condition waiting list
//----------------------------------------------------------------------
void Condition::Wait(Lock* conditionLock)
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //Disable interrupts
	if(conditionLock == NULL)
	{
		printf("Error caught: The lock trying to be used is NULL!\n");
		(void) interrupt->SetLevel(oldLevel); //Restore interrupts
		return;
	}
	if (waitingLock == NULL) //This is the first thread calling wait
	{
	    waitingLock = conditionLock;
	}
	if(waitingLock != conditionLock)
	{
		printf("Error caught: A different lock has already been set for this condition!\n");
		(void) interrupt->SetLevel(oldLevel); //Restore interrupts
		return;
	}
	//Ok to wait
	conditionLock->Release(); //Exit the monitor
	waitingList->Append((void *)currentThread); //Add thread to the condition waiting list
	currentThread->Sleep(); //And put the thread to sleep
	conditionLock->Acquire(); //Enter the monitor
	(void) interrupt->SetLevel(oldLevel); //Restore interrupts
}
//----------------------------------------------------------------------
// Condition::Signal
//  Wake up the next waiting thread in line
//----------------------------------------------------------------------
void Condition::Signal(Lock* conditionLock)
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff); //Disable interrupts
	if(waitingList->IsEmpty()) //If no threads are waiting for the condition
	{
		(void) interrupt->SetLevel(oldLevel); //Restore interrupts
		return;
	}
	if(waitingLock != conditionLock)
	{
		printf("Error caught: The passed lock does not match the lock currently waiting for the condition variable\n");
		(void) interrupt->SetLevel(oldLevel);//restore interrupts
		return;
	}
	Thread* thread = (Thread *)waitingList->Remove(); //Remove the next thread from the condition's waiting list
	scheduler->ReadyToRun(thread); //And wake that thread up
	if(waitingList->IsEmpty()) //If no more waiting threads
	{
		waitingLock = NULL; //Clear the waiting lock
	}
}
//----------------------------------------------------------------------
// Condition::Broadcast
// 	Wake up all threads in the condition waiting list
//----------------------------------------------------------------------
void Condition::Broadcast(Lock* conditionLock)
{
	while(waitingList->IsEmpty() == false) //Wake up all waiting threads
	{
		Signal(conditionLock);
	}
}
